package cn.hdr.train.loadBalance;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;

/**
 * 一致性hash
 * @author: hdr
 * @date: 2020-08-14 14:57
 */
public class ConsistentHashLoadBalance {

    /**
     * 虚拟节点数
     */
    private int vrNodeNum = 128;

    private ConcurrentMap<String,HashCircle> hashCircleMap = new ConcurrentHashMap<>(64);


    public <T> T doSelect(List<T> list,String key,int hash){
        HashCircle<T> hashCircle = hashCircleMap.get(key);
        if(hashCircle == null){
            hashCircleMap.put(key,new HashCircle(list));
            hashCircle = hashCircleMap.get(key);
        }
        return hashCircle.getElement(hash);
    }

    class HashCircle<T>{

        private final long NUM_32 = 1L << 32;
        private final long NUM_31 = 1L << 31;

        private Map<Integer,T> map;
        private int[] hashArr;


        private HashCircle(List<T> list){
            hashArr = new int[list.size() * vrNodeNum];
            map = new HashMap<>(list.size() * vrNodeNum);
            for (int i = 0; i < list.size(); i++) {
                T t = list.get(i);
                for (int j = 0; j < vrNodeNum; j++) {
                    int hash = hash(t,i);
                    hashArr[i * vrNodeNum + j] = hash;
                    map.put(hash,t);
                }
            }

            Arrays.sort(hashArr);
        }

        private int hash(T t,int v){
            //此处hash函数必须具备较好的离散性。
            return Objects.hash(t,v);
        }

        /**
         * 可以认为hash环是分布均匀的在 min - max.
         * 故而可以通过 hash值 大致推测位于数组的位置
         * 而不是从 0 开始遍历
         */
        private T getElement(int hash){
            long zHash = NUM_31 + hash;
            int index = (int)((zHash * 1.0d / NUM_32) * hashArr.length);

            if(hashArr[index] > hash){
                //向前找
                for (; index >= 0 ; index--) {
                    if(hashArr[index] < hash){
                        index++;
                        break;
                    }
                }
            }else if(hashArr[index] < hash){
                //向后找
                for (; index < hashArr.length ; index++) {
                    if(hashArr[index] > hash){
                        break;
                    }
                }
            }

            return map.get(hashArr[index]);
        }
    }

    public static void main(String[] args){
        long NUM_32 = 1L << 32;
        long zHash = 1L << 31;
        int index = (int)((zHash * 1.0d / NUM_32) * 1024);
        System.out.println(index);
    }
}